Problem 437 Path Sum III
该问题属于二叉树问题,要求求出路径和满足给定值的路径数量,不同之处在于以往的求路径问题都是从根结点出发,而该题可以从任意结点出发.
主要思路:
由于任意结点都能成为路径中的根结点,所以相当于增加了遍历这个操作,可以采用任意的方式进行遍历,我采用了队列的形式对结点进行入队操作.当有了根结点后就以它为出发点对其下属的所有路径进行遍历,遍历过程中要注意在递归结束时对值的操作,比如在对叶子结点的值进行累加后,判断它与预设值是否相同,之后需要将其减去,完成类似回退的操作.
代码实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
Queue<TreeNode> queue = new LinkedList<>();
int pathSum = 0;
int paths = 0;
int result = 0;
public int pathSum(TreeNode root, int sum) {
queue = makeQueue(root);
while (!queue.isEmpty()){
TreeNode node = queue.poll();
result += pathSumFromOneNode(node,sum);
paths = 0;
}
return result;
}
public int pathSumFromOneNode(TreeNode root,int sum){
if (root==null){
return 0;
}if (root.left==null&&root.right==null){
pathSum += root.val;
if (pathSum==sum)
paths += 1;
pathSum -= root.val;
return paths;
}
else{
pathSum += root.val;
if (pathSum==sum)
paths += 1;
pathSumFromOneNode(root.left,sum);
pathSumFromOneNode(root.right,sum);
pathSum -= root.val;
}
return paths;
}
public Queue<TreeNode> makeQueue(TreeNode root){
if (root==null){
return queue;
}else {
queue.offer(root);
makeQueue(root.left);
makeQueue(root.right);
}
return queue;
}
}